package com.shuang.dp12;

class Solution {
    //将字符数组每个字符中的0和1的个数作为背包要装的重量 装的字符个数（物品个数）数组的值
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j] 数组表示 0个数的最大容量为i 1个数的最大容量为j 时 的物品的个数（字符串的个数）（即为strs 的最大子集的长度）
        int[][] dp = new int[m + 1][n + 1];

        //递推公式
        //当前i个0 j个1的容量背包 可以装的物品最大个数为dp[i][j]  统计当前遇到的物品（字符串）0和1的个数 如果还能装进来则为前一次物品个数 加 1将当前物品加进来  取最大值 公式如下：
        //dp[i][j] = max(dp[i - zeroNum][j - oneNum] + 1, dp[i][j])

        //初始化 dp[0][0] = 0;容量为零时装的物品个数肯定为0 其余位置 为了不让取最大值时dp[i][j]覆盖公式中的值 全部初始化为0即可

        //遍历顺序 先物品从前到后 再背包倒序

        //用于统计每个字符串中字符0和1的个数
        int zeroNum, oneNum;

        //遍历物品
        for (String str : strs) {
            //取到数组中每个字符串

            // 得到每个字符串时将其中字符0和1的个数初始化为0 在下面遍历字符串统计
            zeroNum = 0;
            oneNum = 0;
            
            for (char c : str.toCharArray()) {
                //取到每个字符串的每个字符
                if (c == '0') {
                    //计算每个字符串字符0的个数
                    zeroNum++;
                } else {
                    // 字符1的个数
                    oneNum++;
                }
            }

            //遍历背包 倒序 先遍历容量0还是容量1无所谓
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i - zeroNum][j - oneNum] + 1, dp[i][j]);
                }
            }

        }

        return dp[m][n];
    }
}